package com.dyz.leetcode._12_linkedList;

import com.dyz.leetcode.ListNode;

public class _234_isPalindrome {
    public boolean isPalindrome(ListNode head) {
        if(head==null|| head.next==null){return true;}
        //快慢指针
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode newHead = slow.next;//下一个节点
        slow.next = null;
        //下个节点反转
        ListNode right = reverse(newHead);
        ListNode left = head;
        while (right!=null){
            if(left.val!=right.val){
                return false;
            }
            left = left.next;
            right = right.next;
        }
        return true;

    }

    private ListNode reverse(ListNode head){
        ListNode prev = null;
        ListNode curr =head;
        while (curr!=null){
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}
